#include "LeetCode.h"

int LeetCode2787::numberOfWays(int n, int x) {
  // 提前准备x次幂，也就是物品
  long long p[n + 1];
  for (int i = 1; i <= n; i++) {
    p[i] = i;
    // 计算x次幂
    for (int j = 1; j <= x; j++) p[i] *= i;
  }

  const long long mod = 1e9 + 7;  // 科学计数法
  // 初始化dp数组，dp[i]表示用物体装满，容量为i的方案数
  vector<int> dp(n + 1, 0);
  // 初始化
  dp[0] = 1;
  // 先遍历物品再遍历背包
  for (int i = 1; i <= n; i++) {
    for (int j = n; j >= p[i]; j--) {
      dp[j] = (dp[j] + dp[j - p[i]]) % mod;
    }
  }
  return dp[n];
}